package wangn;

import java.io.IOException;

/**
 * 红黑树检测类
 * 代码作者：nju computer science and technology department prof. Zhao
 * 注释：王宁，原来的注释乱码
 * 接口总结：
 * 1、toString（） 将红黑树中序遍历标准化输出
 * 2、getBlackHeight（）得到黑高度或者高度约束不满足时候-1
 * 3、checkColor（） 颜色约束是否满足
 * 4、outputElements_Rec(RBTree) 中序打印含有的元素
 * 5、checkOrder（RBTree） 检测二叉搜索树顺序是否满足
 */

public class RBTree {

	static final int RED = 0;
	static final int BLACK = 1;
	
	int key;
	RBTree left, right;
	int color; //0--red, 1--black
	
	
	public RBTree(RBTree l, int k, int c, RBTree r) {
		this.left = l;
		this.key = k;
		this.color = c;
		this.right = r;
	}
	
	
	static String[] testCases = {
			"(NIL, (1,black), NIL)",
			"((NIL, (1,red), NIL), (5,black), (NIL, (7,red), NIL))",
			"(NIL, (5,black), (NIL, (7,red), NIL))",
			"(NIL, (5,black), (NIL, (4,red), NIL))",
			"((NIL, (1,black), NIL), (5,black), (NIL, (7,black), NIL))",
			"((NIL, (1,black), NIL), (5,red), (NIL, (7,black), NIL))",
			"(((NIL, (1,black), NIL), (5,red), (NIL, (7,black), NIL)), (10, black), (NIL, (12,black), NIL))"
		};

	/**
	 * 测试接口样例
	 * @param args
	 */
	public static void main(final String[] args) {
		for(;;)
		{
			String s = getALineFromInput();
			if(s == null || s.length() <= 1)
				break;
			RBTree rbtFromInput = getRBTFromString(s);
			if(rbtFromInput != null)
			{
				System.out.println("Output\t" + rbtFromInput.toString());

				int h = rbtFromInput.getBlackHeight();
				boolean colorCheck = rbtFromInput.checkColor();

				System.out.println("\tColor constraint " + (colorCheck ? "OK" : "broken"));
				System.out.println("\tBlack height " + (h >= 0 ? " is " + h : "constraint broken"));
				System.out.print("\tElements in tree:");
				RBTree.outputElements_Rec(rbtFromInput);
				boolean orderCheck = RBTree.checkOrder(rbtFromInput);
				System.out.println("\n\tOrder constraint " + (orderCheck ? "OK" : "broken"));
			}
		}
		
		for(String s : testCases)
		{
			System.out.println("Input\t" + s);
			RBTree rbt = getRBTFromString(s);
			
			if(rbt == null)
				continue;
			
			System.out.println("Output\t" + rbt.toString());

			int h = rbt.getBlackHeight();
			boolean colorCheck = rbt.checkColor();

			System.out.println("\tColor constraint " + (colorCheck ? "OK" : "broken"));
			System.out.println("\tBlack height " + (h >= 0 ? " is " + h : "constraint broken"));
			System.out.print("\tElements in tree:");
			RBTree.outputElements_Rec(rbt);
			boolean orderCheck = RBTree.checkOrder(rbt);			
			System.out.println("\n\tOrder constraint " + (orderCheck ? "OK" : "broken"));
		}
	}


	/**
	 * @return n如果树的满足各外部节点的黑路径长度相等，否则-1
	 */
	int getBlackHeight()
	{
		int lHeight;
		if(this.left == null)
			lHeight = 1;
		else
		{
			lHeight = this.left.getBlackHeight();
			if(lHeight < 0)
				return -1;
		}
		
		int rHeight;
		if(this.right == null)
			rHeight = 1;
		else
		{
			rHeight = this.right.getBlackHeight();
			if(rHeight < 0)
				return -1;
		}
		
		if(lHeight == rHeight)
			return lHeight + (this.color == BLACK ? 1 : 0);
		
		return -1;
	}

	private static boolean checkOrder(RBTree rbt)
	{
		curValue = -1;
		return checkOrder_Rec(rbt);
	}

	private static int curValue;
	/**
	 * @param rbt 当前节点
	 * @return 是否满足二叉搜索树的顺序
	 */
	private static boolean checkOrder_Rec(RBTree rbt)
	{
		if(rbt == null)
			return true;
		
		if(!checkOrder_Rec(rbt.left))
			return false;
		
		if(rbt.key < curValue)
			return false;
		curValue = rbt.key;
		
		if(!checkOrder_Rec(rbt.right))
			return false;
		
		return true;
	}

	private static boolean outputElements_Rec(RBTree rbt)
	{
		if(rbt == null)
			return true;
		
		if(!outputElements_Rec(rbt.left))
			return false;
		
		System.out.print("\t" + rbt.key);
		
		if(!outputElements_Rec(rbt.right))
			return false;
		
		return true;
	}

	/**
	 * @return 是否满足颜色约束
	 */
	boolean checkColor()
	{
		int leftColor;
		if(this.left == null)
			leftColor = BLACK;
		else
		{
			if(!this.left.checkColor())
				return false;
			leftColor = this.left.color;
		}
		int rightColor;
		if(this.right == null)
			rightColor = BLACK;
		else
		{
			if(!this.right.checkColor())
				return false;
			rightColor = this.right.color;
		}
		
		if(this.color == BLACK)
			return true;
		if(leftColor == RED || rightColor == RED)
			return false;
		return true;
	}
	
	
	public String toString()
	{
		String s = "(";
		if(this.left == null)
			s += "NIL";
		else 
			s += this.left.toString();
		s += ", (";
		s += "" + this.key + "," + (this.color == RED ? "red" : "black") + "), ";
	
		if(this.right == null)
			s += "NIL";
		else 
			s += this.right.toString();
		
		s += ")";
		
		return s;
	}

	
	static String errorMsg;
	static int nextChar;
	static int nextPos;
	static char[] inputBuf;
	static String scannedInput;
	
	
	/*
	 * 从输入中构造RBT
	 */
	static RBTree getRBTFromString(String s)
	{
		inputBuf = s.toCharArray();
		errorMsg = null;
		nextChar = inputBuf[0];
		nextPos = 0;
		
		RBTree rbt =  getRBTFromInput_Rec();
		if(errorMsg != null)
		{
			System.out.println("\t" + s.substring(0,nextPos));
			System.out.println("\t" + errorMsg);
			return null;
		}
		return rbt;
	}

/****************************************************************************************************/
	//下面对缓冲区的字符逐个进行扫描，构建红黑树，子程序在后面
/****************************************************************************************************/
	private static RBTree getRBTFromInput_Rec()
	{
		if(tryToGetNIL())
			return null;
		
		getLeftPara();
		if(errorMsg != null)
			return null;
		
		RBTree left = getRBTFromInput_Rec();
		if(errorMsg != null)
			return null;

		getCOMMA();
		if(errorMsg != null)
			return null;

		getLeftPara();
		if(errorMsg != null)
			return null;

		int key = getInteger();
		if(errorMsg != null)
			return null;

		getCOMMA();
		if(errorMsg != null)
			return null;

		int color = getCOLOR();
		if(errorMsg != null)
			return null;

		getRightPara();
		if(errorMsg != null)
			return null;

		getCOMMA();
		if(errorMsg != null)
			return null;

		RBTree right = getRBTFromInput_Rec();
		if(errorMsg != null)
			return null;

		getRightPara();
		if(errorMsg != null)
			return null;

		return new RBTree(left, key, color, right);
	}
	
	private static void getCOMMA() {
		skipBlank();
		if(nextChar == ',')
		{
			nextChar = getAChar();
			skipBlank();
		}
		else
		{
			errorMsg = "\',\' expected!";
		}
	}

	private static void getLeftPara() {
		skipBlank();
		if(nextChar == '(')
		{
			nextChar = getAChar();
			skipBlank();
		}
		else
		{
			errorMsg = "\'(\' expected!";
		}
	}

	private static void getRightPara() {
		skipBlank();
		if(nextChar == ')')
		{
			nextChar = getAChar();
			skipBlank();
		}
		else
		{
			errorMsg = "\')\' expected!";
		}
	}

	static private boolean tryToGetNIL() {
		int prevPos = nextPos;
		skipBlank();
		String id = getID();
		if ("NIL".equals(id))
			return true;
		
		nextPos = prevPos;
		nextChar = nextPos < inputBuf.length ? inputBuf[nextPos] : -1;
			
//		errorMsg = "\"NIL\" expected.";
		return false;
	}

	private static int getCOLOR() {
		skipBlank();
		String id = getID();
		if("black".equals(id))
			return BLACK;
		else if("red".equals(id))
			return RED;
		else
			errorMsg = "Black/Red expected.";
		return -1;
	}


	
	private static String getID() {
		String ret = "";
		while((nextChar >= 'a' && nextChar <= 'z')|| (nextChar >= 'A' && nextChar <= 'Z'))
		{
			ret += (char)nextChar;
			nextChar = getAChar();
		}
		return ret;
	}

	private static int getInteger() {
		int ret = 0;
		while(nextChar >= '0' && nextChar <= '9')
		{
			ret = ret * 10 + (nextChar - '0'); 
			nextChar = getAChar();
		}
		if((nextChar >= 'a' && nextChar <= 'z')|| (nextChar >= 'A' && nextChar == 'Z'))
		{
			errorMsg = "A char following an integer.";
		}
		return ret;
	}


	private static void skipBlank() {
		while(nextChar == ' ' || nextChar == '\n' || nextChar == '\t')
			nextChar = getAChar();
	}
	
	private static int getAChar()
	{
		nextPos ++;
		if(nextPos >= inputBuf.length)
			nextChar = -1;
		else
			nextChar = inputBuf[nextPos];
		return nextChar;
	}

	/**
	 * @return 从标注输入读入字符串，每次读入一行
	 */
	private static String getALineFromInput() {
		String ret = "";
		for(;;)
		{
			int nChar;
			try {
				nChar = System.in.read();
			} catch (IOException e) {
				return null;
			}
			if(nChar == '\n')
				break;
			ret += (char)nChar;
		}
		return ret;
	}


}
